package optplanner;

import java.util.ArrayList;
import java.util.Collection;

import engine.planner.QueryData;
import engine.planner.QueryPlanner;
import engine.query.Plan;
import engine.query.ProjectPlan;

import storage.tx.Transaction;

/**
 * A query planner that optimizes using a greedy algorithm.
 * @author Edward Sciore
 */
public class OptimizedQueryPlanner implements QueryPlanner {
	private Collection<TablePlanner> tableinfo = new ArrayList<TablePlanner>();

	/**
	 * Creates an optimized left-deep query plan using the following 
	 * greedy strategy.
	 * Chose the smallest table (considering selection predicates)
	 * to be first in the join order.
	 * Then repeatedly add the table to the join order which 
	 * results in the smallest output. 
	 */
	public Plan createPlan(QueryData data, Transaction tx) {

	// Step 1:  Create a TablePlanner object for each mentioned table
		for (String tblname : data.tables()) {
			TablePlanner tp = new TablePlanner(tblname, data.pred(), tx);
			tableinfo.add(tp);
		}

	// Step 2:  Choose the lowest-size plan to begin the join order
		Plan currentplan = getLowestSelectPlan();

	// Step 3:  Repeatedly add a plan to the join order
		while (!tableinfo.isEmpty()) {
			Plan p = getLowestJoinPlan(currentplan);
			if (p != null)
				currentplan = p;
			else  // no applicable join
				currentplan = getLowestProductPlan(currentplan);
		}

	// Step 4.  Project on the field names and return
		return new ProjectPlan(currentplan, data.fields());
	}
	private Plan getLowestSelectPlan() {
		TablePlanner besttp = null;
		Plan bestplan = null;
		for (TablePlanner tp : tableinfo) {
			Plan plan = tp.makeSelectPlan();
			if (bestplan == null || plan.recordsOutput() < bestplan.recordsOutput()) {
				besttp = tp;
				bestplan = plan;
			}
		}
		tableinfo.remove(besttp);
		return bestplan;
	}

	private Plan getLowestJoinPlan(Plan current) {
		TablePlanner besttp = null;
		Plan bestplan = null;
		for (TablePlanner tp : tableinfo) {
			Plan plan = tp.makeJoinPlan(current);
			if (plan != null && (bestplan == null || plan.recordsOutput() < bestplan.recordsOutput())) {
				besttp = tp;
				bestplan = plan;
			}
		}
		if (bestplan != null)
			tableinfo.remove(besttp);
		return bestplan;
	}

	private Plan getLowestProductPlan(Plan current) {
		TablePlanner besttp = null;
		Plan bestplan = null;
		for (TablePlanner tp : tableinfo) {
			Plan plan = tp.makeProductPlan(current);
			if (bestplan == null || plan.recordsOutput() < bestplan.recordsOutput()) {
				besttp = tp;
				bestplan = plan;
			}
		}
		tableinfo.remove(besttp);
		return bestplan;
	}
}
